Search for: All records

Chemical reaction networks (CRNs) model systems where molecules interact according to a finite set of reactions such as A + B → C, representing that if a molecule of A and B collide, they disappear and a molecule of C is produced. CRNs can compute Boolean-valued predicates ϕ:ℕ^d → {0,1} and integer-valued functions f:ℕ^d → ℕ; for instance X₁ + X₂ → Y computes the function min(x₁,x₂), since starting with x_i copies of X_i, eventually min(x₁,x₂) copies of Y are produced. We study the computational power of execution bounded CRNs, in which only a finite number of reactions can occur from the initial configuration (e.g., ruling out reversible reactions such as A ⇌ B). The power and composability of such CRNs depend crucially on some other modeling choices that do not affect the computational power of CRNs with unbounded executions, namely whether an initial leader is present, and whether (for predicates) all species are required to "vote" for the Boolean output. If the CRN starts with an initial leader, and can allow only the leader to vote, then all semilinear predicates and functions can be stably computed in O(n log n) parallel time by execution bounded CRNs. However, if no initial leader is allowed, all species vote, and the CRN is "non-collapsing" (does not shrink from initially large to final O(1) size configurations), then execution bounded CRNs are severely limited, able to compute only eventually constant predicates. A key tool is a characterization of execution bounded CRNs as precisely those with a nonnegative linear potential function that is strictly decreased by every reaction [Czerner et al., 2024]. 

The relationship between the thermodynamic and computational properties of physical systems has been a major theoretical interest since at least the 19th century. It has also become of increasing practical importance over the last half-century as the energetic cost of digital devices has exploded. Importantly, real-world computers obey multiple physical constraints on how they work, which affects their thermodynamic properties. Moreover, many of these constraints apply to both naturally occurring computers, like brains or Eukaryotic cells, and digital systems. Most obviously, all such systems must finish their computation quickly, using as few degrees of freedom as possible. This means that they operate far from thermal equilibrium. Furthermore, many computers, both digital and biological, are modular, hierarchical systems with strong constraints on the connectivity among their subsystems. Yet another example is that to simplify their design, digital computers are required to be periodic processes governed by a global clock. None of these constraints were considered in 20th-century analyses of the thermodynamics of computation. The new field of stochastic thermodynamics provides formal tools for analyzing systems subject to all of these constraints. We argue here that these tools may help us understand at a far deeper level just how the fundamental thermodynamic properties of physical systems are related to the computation they perform. 

Understanding the algorithmic behaviors that are in principle realizable in a chemical system is necessary for a rigorous understanding of the design principles of biological regulatory networks. Further, advances in synthetic biology herald the time when we will be able to rationally engineer complex chemical systems and when idealized formal models will become blueprints for engineering. Coupled chemical interactions in a well-mixed solution are commonly formalized as chemical reaction networks (CRNs). However, despite the widespread use of CRNs in the natural sciences, the range of computational behaviors exhibited by CRNs is not well understood. Here, we study the following problem: What functions f : ℝ k → ℝ can be computed by a CRN, in which the CRN eventually produces the correct amount of the “output” molecule, no matter the rate at which reactions proceed? This captures a previously unexplored but very natural class of computations: For example, the reaction X 1 + X 2 → Y can be thought to compute the function y = min ( x 1 , x 2 ). Such a CRN is robust in the sense that it is correct whether its evolution is governed by the standard model of mass-action kinetics, alternatives such as Hill-function or Michaelis-Menten kinetics, or other arbitrary models of chemistry that respect the (fundamentally digital) stoichiometric constraints (what are the reactants and products?). We develop a reachability relation based on a broad notion of “what could happen” if reaction rates can vary arbitrarily over time. Using reachability, we define stable computation analogously to probability 1 computation in distributed computing and connect it with a seemingly stronger notion of rate-independent computation based on convergence in the limit t → ∞ under a wide class of generalized rate laws. Besides the direct mapping of a concentration to a nonnegative analog value, we also consider the “dual-rail representation” that can represent negative values as the difference of two concentrations and allows the composition of CRN modules. We prove that a function is rate-independently computable if and only if it is piecewise linear (with rational coefficients) and continuous (dual-rail representation), or non-negative with discontinuities occurring only when some inputs switch from zero to positive (direct representation). The many contexts where continuous piecewise linear functions are powerful targets for implementation, combined with the systematic construction we develop for computing these functions, demonstrate the potential of rate-independent chemical computation. 

The field of chemical computation attempts to model computational behavior that arises when molecules, typically nucleic acids, are mixed together. By modeling this physical phenomenon at different levels of specificity, different operative computational behavior is observed. Thermodynamic binding networks (TBNs) is a highly abstracted model that focuses on which molecules are bound to each other in a "thermodynamically stable" sense. Stability is measured based only on how many bonds are formed and how many total complexes are in a configuration, without focusing on how molecules are binding or how they became bound. By defocusing on kinetic processes, TBNs attempt to naturally model the long-term behavior of a mixture (i.e., its thermodynamic equilibrium). We study the problem of signal amplification: detecting a small quantity of some molecule and amplifying its signal to something more easily detectable. This problem has natural applications such as disease diagnosis. By focusing on thermodynamically favored outcomes, we seek to design chemical systems that perform the task of signal amplification robustly without relying on kinetic pathways that can be error prone and require highly controlled conditions (e.g., PCR amplification). It might appear that a small change in concentrations can result in only small changes to the thermodynamic equilibrium of a molecular system. However, we show that it is possible to design a TBN that can "exponentially amplify" a signal represented by a single copy of a monomer called the analyte: this TBN has exactly one stable state before adding the analyte and exactly one stable state afterward, and those two states "look very different" from each other. In particular, their difference is exponential in the number of types of molecules and their sizes. The system can be programmed to any desired level of resilience to false positives and false negatives. To prove these results, we introduce new concepts to the TBN model, particularly the notions of a TBN’s entropy gap to describe how unlikely it is to be observed in an undesirable state, and feed-forward TBNs that have a strong upper bound on the number of polymers in a stable configuration. We also show a corresponding negative result: a doubly exponential upper bound, meaning that there is no TBN that can amplify a signal by an amount more than doubly exponential in the number and sizes of different molecules that comprise it. We leave as an open question to close this gap by either proving an exponential upper bound, or giving a construction with a doubly-exponential difference between the stable configurations before and after the analyte is added. Our work informs the fundamental question of how a thermodynamic equilibrium can change as a result of a small change to the system (adding a single molecule copy). While exponential amplification is traditionally viewed as inherently a non-equilibrium phenomenon, we find that in a strong sense exponential amplification can occur at thermodynamic equilibrium as well - where the "effect" (e.g., fluorescence) is exponential in types and complexity of the chemical components. 

Discrete chemical reaction networks formalize the interactions of molecular species in a well-mixed solution as stochastic events. Given their basic mathematical and physical role, the computational power of chemical reaction networks has been widely studied in the molecular programming and distributed computing communities. While for Turing-universal systems there is a universal measure of optimal information encoding based on Kolmogorov complexity, chemical reaction networks are not Turing universal unless error and unbounded molecular counts are permitted. Nonetheless, here we show that the optimal number of reactions to generate a specific count x ∈ ℕ with probability 1 is asymptotically equal to a "space-aware" version of the Kolmogorov complexity of x, defined as K̃s(x) = min_p {|p|/log|p| + log(space(𝒰(p))) : 𝒰(p) = x}, where p is a program for universal Turing machine 𝒰. This version of Kolmogorov complexity incorporates not just the length of the shortest program for generating x, but also the space usage of that program. Probability 1 computation is captured by the standard notion of stable computation from distributed computing, but we limit our consideration to chemical reaction networks obeying a stronger constraint: they "know when they are done" in the sense that they produce a special species to indicate completion. As part of our results, we develop a module for encoding and unpacking any b bits of information via O(b/log{b}) reactions, which is information-theoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical self-organization can be encoded - in the sense of generating precise molecular counts of species as the desired state. 

We present an abstract model of self-assembly of systems composed of "crisscross slats", which have been experimentally implemented as a single-stranded piece of DNA [Minev et al., 2021] or as a complete DNA origami structure [Wintersinger et al., 2022]. We then introduce a more physically realistic *kinetic* model and show how important constants in the model were derived and tuned, and compare simulation-based results to experimental results [Minev et al., 2021; Wintersinger et al., 2022]. Using these models, we show how we can apply optimizations to designs of slat systems in order to lower the numbers of unique slat types required to build target structures. In general, we apply two types of techniques to achieve greatly reduced numbers of slat types. Similar to the experimental work implementing DNA origami-based slats, in our designs the slats oriented in horizontal and vertical directions are each restricted to their own plane and sets of them overlap each other in square regions which we refer to as macrotiles. Our first technique extends their previous work of reusing slat types within macrotiles and requires analyses of binding domain patterns to determine the potential for errors consisting of incorrect slat types attaching at undesired translations and reflections. The second technique leverages the power of algorithmic self-assembly to efficiently reuse entire macrotiles which self-assemble in patterns following designed algorithms that dictate the dimensions and patterns of growth. Using these designs, we demonstrate that in kinetic simulations the systems with reduced numbers of slat types self-assemble more quickly than those with greater numbers. This provides evidence that such optimizations will also result in greater assembly speeds in experimental systems. Furthermore, the reduced numbers of slat types required have the potential to vastly reduce the cost and number of lab steps for crisscross assembly experiments.